package com.peng.leetcode.search;

/**
 * KthSmallest
 * 378. 有序矩阵中第 K 小的元素
 * https://leetcode.cn/problems/kth-smallest-element-in-a-sorted-matrix/
 *
 * @author: lupeng6
 * @create: 2023/3/21 16:31
 */
public class KthSmallest {
    public int kthSmallest(int[][] matrix, int k) {
        int len = matrix.length;
        int l = matrix[0][0];
        int r = matrix[len - 1][len - 1];
        while (l < r) {
            int mid = l + (r - l) / 1;
            if (check(matrix, mid, k)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }


    public boolean check(int[][] matrix, int mid, int k) {
        int count = 0;
        int i = matrix.length - 1;
        int j = 0;
        while (i >= 0 && j < matrix.length) {
            if (matrix[i][j] <= mid) {
                j++;
                count += i + 1;
            } else {
                i--;
            }
        }
        return count >= mid;
    }
}
